/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.easy._125;

/**
 * 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
 * <p>
 * 说明：本题中，我们将空字符串定义为有效的回文串。
 * <p>
 * 示例 1:
 * <p>
 * 输入: "A man, a plan, a canal: Panama"
 * 输出: true
 * 示例 2:
 * <p>
 * 输入: "race a car"
 * 输出: false
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.easy._125
 * @ClassName: ValidPalindrome
 * @Author: linyaonan
 * @Date: 2019/11/6 16:03
 */
public class ValidPalindrome {
    public boolean isPalindrome(String s) {
        if (s == null || "".equals(s) || s.length() == 1) {
            return true;
        }

        char[] chars = s.toLowerCase().toCharArray();
        StringBuilder builder = new StringBuilder();
        for (char aChar : chars) {
            if (String.valueOf(aChar).matches("[a-z0-9]")) {
                builder.append(aChar);
            }
        }

        int length = builder.length();
        for (int i = 0; i < length; i++) {
            char start = builder.charAt(i);
            char end = builder.charAt(length - 1 - i);
            if (start != end) {
                return false;
            }
        }
        return true;
    }

    /**
     * 双指针
     *
     * @param s
     * @return
     */
    public boolean isPalindrome2(String s) {
        if (s == null || s.isEmpty()) {
            return true;
        }

        int l = 0;
        int r = s.length() - 1;

        while (l < r) {
            while (l<s.length() - 1 && !check(s.charAt(l))) {
                l++;
            }
            while (r >0 && !check(s.charAt(r))) {
                r--;
            }

            if (l >= r) {
                return true;
            }

            if (Character.toLowerCase(s.charAt(l)) != Character.toLowerCase(s.charAt(r))) {
                return false;
            }
            l++;
            r--;
        }

        return true;
    }

    private boolean check(char c) {
        return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9');
    }

}



